# !/usr/bin/env python
# -*- coding: utf-8 -*-
"""
@Time        : 2021/4/22 21:42
@Author      : Albert Darren
@Contact     : 2563491540@qq.com
@File        : pack.py
@Version     : Version 1.0.0
@Description : TODO
@Created By  : PyCharm
"""


def pack_boxes(weight_seq, box_weight=10):
    weight_seq = sorted(weight_seq, reverse=True)  # 将数据由大到小排序
    j = len(weight_seq) - 1
    count = 1
    boxes = {}
    for i in range(j + 1):
        weight_sum = weight_seq[i]
        boxes[count] = []
        boxes[count].append(weight_seq[i])
        while j >= i:
            weight_sum += weight_seq[j]
            if weight_sum > box_weight:
                count += 1
                break
            boxes[count].append(weight_seq[j])
            j -= 1
    return boxes, count


def task_least_time(k, t, job):
    # 计算每个工人理想的平均花费时间
    avg_time = sum(job) / k
    # begin_index: 0 ~ len(job) - 1
    begin_index = 0
    # return final_time * t
    final_time = 0
    # 如果len(job) - begin_index == k 或者 k == 1，则剩下的活一人一个
    while len(job) - begin_index > k > 1:
        current_time = job[begin_index]
        begin_index += 1
        for endIdx in range(begin_index, len(job) - k + 1):
            # 选择与平均消耗时间最接近的组合
            if abs(current_time - avg_time) > abs(current_time + job[endIdx] - avg_time):
                current_time += job[endIdx]
                begin_index += 1
            else:
                break
        final_time = max(final_time, current_time)
        k -= 1
    final_time = max(final_time, max(job[begin_index:]))
    return final_time * t


if __name__ == '__main__':
    # 习题8-1
    article_weights = [8, 7, 9, 7, 5, 2, 4, 3, 1, 4, 1, 6, 6, 5, 3, 5, 8, 6, 5, 4, 2, 8, 1, 5, 6]
    pack_ways, box_num = pack_boxes(article_weights)
    # 验证不重复不遗漏，证明算法正确性
    article_weights.sort(reverse=True)
    result_ls = []
    for i in pack_ways:
        result_ls.extend(pack_ways[i])
    result_ls.sort(reverse=True)
    print('排序后的原始物品重量列表:{}\n最少箱子分配方案重量列表:{}'.format(article_weights, result_ls))
    print('最少箱子数为:{}个\n装箱方案为:{}'.format(box_num, pack_ways))
    # 习题8-2
    occupation = [8, 7, 9, 7, 5, 2, 4, 3, 1, 4, 1, 6, 6, 5, 3, 5, 8, 6, 5, 4, 2, 8, 1, 5, 6]
    print('完成任务的最小时间为:{}'.format(task_least_time(k=6, t=5, job=occupation)))
